#include <vector>
#include <unordered_map>
using namespace std;
class Solution
{
public:
    // sum(i, j) = sum(0, j) - sum(0, i - 1) = tk
    // sum(0, i - 1) = sum(0, j) - tk;
    // 也就是说找到和sum(0,j)%k相同的数有几个
    // 由于c++的特殊机制，所以需要用到最小整数解
    inline int mod(int a, int b) { return (a % b + b) % b; }
    int subarraysDivByK(vector<int> &nums, int k)
    {
        unordered_map<int, int> hash;
        hash[0] = 1;
        int ans = 0;
        for (int i = 0, sum = 0; i < nums.size(); ++i)
        {
            sum += nums[i];
            if (hash.count(mod(sum, k)))
                ans += hash[mod(sum, k)];
            hash[mod(sum, k)]++;
        }
        return ans;
    }
};